// https://leetcode-cn.com/problems/product-of-array-except-self/

class Solution {
public:
    // 法一：左右乘积数组
    // vector<int> productExceptSelf(vector<int>& nums) {
    //     int n = nums.size();
    //     vector<int> front(n);
    //     vector<int> back(n);
    //     vector<int> output(n);
    //     front[0] = nums[0];
    //     back[n - 1] = nums[n - 1];
    //     for (int i = 1; i < n; ++i) {
    //         front[i] = front[i - 1] * nums[i];
    //     }
    //     for (int i = n - 2; i >= 0; --i) {
    //         back[i] = back[i + 1] * nums[i];
    //     }
    //     output[0] = back[1];
    //     output[n - 1] = front[n - 2];
    //     for (int i = 1; i < n - 1; ++i) {
    //         output[i] = back[i + 1] * front[i - 1];
    //     }
    //     return output;
    // }

    // 法二：空间优化
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> output(n);
        output[0] = 1;
        // output[i] 表示索引 i 左侧所有元素的乘积
        for (int i = 1; i < n; ++i) {
            output[i] = output[i - 1] * nums[i - 1];
        }
        int r = 1;
        for (int i = n - 1; i >= 0; --i) {
            output[i] *= r;
            r *= nums[i];
        }
        return output;
    }
};